1. Field of the Invention
The invention relates to programmable integrated circuit devices, more particularly to an expandable interconnect structure in a field programmable logic device.
2. Description of the Background Art
Field programmable gate arrays (FPGAs) include logic blocks connectable through a programmable interconnect structure. The interconnect structure typically provides for connecting each logic block to each other logic block. Early FPGAs accomplished this by providing short interconnect segments that could be joined to each other and to input and output terminals of the logic blocks at programmable interconnection points (PIPs). As these FPGAs become larger and more complex, the interconnect structure must also become both larger and more complex. In order to improve speed (performance), direct connections to adjacent logic blocks have been provided, and for transmitting a signal the distance of many logic blocks, longer lines have been provided. In order to save silicon area, less frequent PIPs have been provided. With fewer PIPs present, the routing is less flexible (for the same number of routing lines), but typically faster due to reduced loading. By removing only those PIPs which are least often used, routing flexibility can be minimally affected. Thus, there is a trade-off between performance, silicon area, number of routing lines, and routing flexibility.
Several U.S. Patents show such structures for interconnecting logic blocks in FPGAs. Freeman in U.S. Reissue Pat. Re No. 34,363 describes the first FPGA interconnect structure, and includes short routing segments and flexible connections as well as global lines for signals such as clock signals. Carter in U.S. Pat. No. 4,642,487 shows the addition of direct connections between adjacent logic blocks to the interconnect structure of Freeman. These direct connections provide fast paths between adjacent logic blocks. Greene et al in U.S. Pat. No. 5,073,729 shows a segmented interconnect structure with routing lines of varied lengths. Kean in U.S. Pat. No. 5,469,003 shows a hierarchical interconnect structure having lines of a short length connectable at boundaries to lines of a longer length extending between the boundaries, and larger boundaries with lines of even longer length extending between those boundaries. Kean shows in particular lines the length of one logic block connecting each logic block to the next, lines the length of four logic blocks connectable to each logic block they pass, and lines the length of sixteen logic blocks connectable at the length-four boundaries to the length-four lines but not connectable directly to the logic blocks. In Kean""s architecture, adjacent logic blocks in two different hierarchical blocks (i.e., on either side of the boundaries) connect to each other differently than adjacent logic blocks in the same hierarchical block.
Pierce et al in U.S. Pat. No. 5,581,199 shows a tile-based interconnect structure with lines of varying lengths in which each tile in a rectangular array may be identical to each other tile. In the Pierce et al architecture, an interconnect line is part of the output structure of a logic block. Output lines of more than one length extend past other logic block input lines to which the logic block output lines can be connected. All of the above-referenced patents are incorporated herein by reference, and can be reviewed for more understanding of prior art routing structures in FPGAs.
In the interconnect structures described by Freeman and Greene et al, each path is formed by traversing a series of programmable concatenated interconnect lines, i.e., a series of relatively short interconnect lines are programmably connected end to end to form a longer path. The relatively large number of programmable connections on a given signal path introduces delay into the signal path and therefore reduces the performance of the FPGA. Such interconnect structures are called xe2x80x9cgeneral interconnectxe2x80x9d.
The direct connections first described by Carter and included in the architecture of Kean provide fast paths between adjacent logic blocks, but in Carter""s structure general interconnect must still be used to traverse the distance between any two blocks that are not adjacent. Therefore, circuits large enough or complex enough to require interconnecting signals between non-adjacent blocks (which frequently occur) must use the general interconnect to make these connections. For short paths, general interconnect is slower than direct interconnect, because general interconnect must be connected through several PIPs, or, if long lines are used, must be buffered to accommodate long or heavily loaded signals, introducing delay. Additionally, it is inefficient in terms of silicon area to use long lines for short paths that may be traversing only a few logic blocks, since the long lines can otherwise be used for longer paths. Further, since software that implements a logic design in an FPGA typically places interconnected logic in close proximity, structures that take advantage of this placement strategy will work well with the software, resulting in shorter compilation times for routing software and more efficient circuit implementations.
Interconnect lines called xe2x80x9cquad linesxe2x80x9d are included in the XC4000EX FPGAs from Xilinx, Inc., and described on pages 4-32 through 4-37 of the Xilinx 1996 Data Book entitled xe2x80x9cThe Programmable Logic Data Bookxe2x80x9d, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, which are incorporated herein by reference. However, since each quad line contacts every tile that it traverses, these lines have a large number of PIPs, each of which adds RC delay.
Pierce et al provides fast paths between both adjacent logic blocks and logic blocks several tiles apart. The output lines of the Pierce et al architecture can each drive the inputs of a limited set of other logic blocks. However, the possible destinations are limited to selected logic blocks, and the interconnect lines can only access certain specific inputs of the destination logic blocks.
In each of the prior art structures recited above, each interconnect line has programmable connections to the inputs of other logic blocks. However, in the structures of Freeman, Carter, and Pierce et al, a given logic block input can be driven from either horizontal interconnect lines, or vertical interconnect lines, but not both. An alternative approach is to separate the interconnect lines from the logic block inputs by way of a routing matrix, which gives each interconnect line more flexible access to the logic block inputs. Such an architecture is described in U.S. Pat. No. 5,682,107, entitled xe2x80x9cFPGA Architecture With Repeatable Tiles Including Routing Matrices and Logic Matricesxe2x80x9d by Tavana et al, which is incorporated herein by reference. In the structure of Tavana et al, most interconnect lines entering the tile connect to a routing matrix within the tile, rather than directly to logic block inputs or outputs. Connections between pairs of interconnect lines and between interconnect lines and logic block inputs are made through lines called xe2x80x9ctile interconnect linesxe2x80x9d that do not leave the tile. The advantage of having an extra interconnect line in a path from the edge of a tile to the logic block in the tile is that the routing matrix is flexible but consumes a relatively small amount of silicon area. A combination of PIPs can allow access from any line entering the tile to any desired input of a destination logic block. Yet the total number of PIPs is smaller than in many other interconnect structures. The disadvantage is that getting on and off the tile interconnect lines inserts a certain amount of delay into the path for each tile traversed. This delay inhibits the fast propagation of signals through the FPGA. Tavana et al have therefore provided long lines connectable to every tile they pass and double-length lines that bypass the tile interconnect lines in one tile. These lines can be used for signals that are traversing one or more tiles without accessing the logic blocks in the traversed tiles.
Kean separates the interconnect lines from the logic block inputs using input multiplexer switches, which provide routing flexibility to the inputs.
Since the slowest signal path between logic blocks typically determines the performance of a circuit, it is advantageous to make the slowest path as fast as possible. One way to accomplish this is to design the interconnect structure such that there is a relatively uniform delay on all signal paths throughout an FPGA. In the above routing structures, a typical distribution of delays on signal paths shows a few signal paths with significantly greater delay than the average. These signal paths are typically those with large xe2x80x9cRC treesxe2x80x9d, i.e., signal paths which traverse a resistor (such as an unbuffered PIP), then have a large capacitance on the destination side of the resistor. An interconnect structure with relatively uniform delay could be better realized if large capacitances on a signal path (e.g., longer interconnect lines) were predictably placed on the source side of the resistor, or as close as possible to the source end of the signal path.
High fanout signals have large capacitance and are often slower than low fanout signals. Prior art routing structures had high-fanout signal routing with relatively large RC delay. An interconnect structure should ideally provide high-fanout signal routing with a delay comparable to that of other signals.
It is therefore desirable to find an interconnect structure that allows: 1) uniformly fast propagation of signals, including high-fanout signals, throughout the FPGA; 2) implementation of localized circuits in non-adjacent as well as adjacent blocks using fast paths; 3) ease of use by software; 4) efficient implementation of commonly used logic functions; and 5) a high degree of routing flexibility per silicon area consumed.
According to the invention, an FPGA interconnect structure includes a combination of wiring segment lengths and connections to logic blocks such that a given logic block can be connected through fast paths both to adjacent logic blocks and to logic blocks several tiles away. In the preferred mode, the FPGA includes a two-dimensional array of identical tiles. In each tile is a logic block. Also in each tile are programmable interconnection points (PIPs) and segments of interconnect lines that adjoin segments of interconnect lines in adjacent tiles. The adjoined segments form interconnect lines extending through several tiles to PIPs in other tiles some distance away. A combination of lines connecting to adjacent tiles (called single-length lines) and lines at least three tiles long connecting a first tile to at least second and third tiles at least two and three tiles away (called intermediate-length lines) creates an interconnect hierarchy which allows any logic block to be connected to any other logic block, and yet also allows for fast paths both to adjacent tiles and to tiles some distance away. Longer interconnect lines (called long lines) may be included as a third level of hierarchy to permit efficient interconnection of widely separated tiles. Long lines can span the entire width of the tile array, or can be programmably segmented into two or more shorter long lines. In one embodiment, long lines are distinguished from intermediate-length lines in that a pattern of PIPs spanning two or more tiles is repeated along the length of the long line. When the size of the tile array is increased, more instances of the pattern occur. By contrast, intermediate-length lines according to the invention are of a predetermined length that does not alter when the size of the array is increased. When the size of the tile array is increased, additional intermediate-length lines are added.
A unique aspect of the invention is having an interconnect line (specifically an intermediate-length line or a long line) that programmably connects to logic blocks in at least three separate tiles, while extending through at least one tile in which no PIPs connect to the interconnect line. Such an interconnect line is said to be xe2x80x9cunconnectablexe2x80x9d to the tile in which no PIPs connect to the interconnect line and also xe2x80x9cunconnectablexe2x80x9d to the logic block in the tile, although connections can be made from the interconnect line to the logic block through PIPs in other tiles. A programmable connection from an interconnect line to a logic block in a given tile may be made: a) directly to a logic block input; b) through one or more PIPs connected to the interconnect line in the same tile; or c) through one or more PIPs connected to the interconnect line in the same tile and through one or more single-length lines. If any such programmable connection from an interconnect line to a logic block in a given tile can be made, the interconnect line is said to be xe2x80x9cconnectablexe2x80x9d to the logic block and to the tile.
In a preferred embodiment, from an originating tile an intermediate-length line connects to the tile three tiles away (i.e., separated by two tiles from the originating tile), then continues and connects to the tile six tiles away (i.e., separated by five tiles from the originating tile). This intermediate-length line (called a xe2x80x9chex linexe2x80x9d) does not connect to the intervening tiles one, two, four, and five tiles away. Instead, these tiles are reached indirectly by using single-length lines from the originating tile, the third tile, or the sixth tile. Connecting to only three of the seven tiles traversed by the hex line reduces the number of PIPs, and therefore reduces the silicon area required to form the interconnect line (thereby lowering the cost of the FPGA) and also reduces the capacitance added by PIPs (thereby increasing FPGA performance). Yet the combination of this intermediate-length routing, direct connections to neighboring tiles, and long lines to distant tiles allows highly flexible routing of signals.
Many modifications of the interconnect structure of the invention are possible. One such modification is the use of asymmetrical PIP patterns on interconnect lines (intermediate-length lines or long lines) such that the interconnect line connects three logic blocks, with two of the three logic blocks being in adjacent tiles, while the third logic block is in a tile separated from the other two tiles.
As FPGAs grow larger, the amount of routing required per tile grows larger. Therefore, the silicon area required to implement the necessary PIPs tends to grow larger, and the silicon area per tile increases as the number of tiles in an FPGA increases. It is desirable to reduce the number of PIPs required per tile.
In one embodiment, only the single-length lines have connections to the logic block inputs. The intermediate-length lines have connections to each other and to single-length lines, but not to the logic block inputs. The long lines have connections to the intermediate-length lines, but not to the single-length lines or to the logic block inputs. Therefore, the number of PIPs in a tile is reduced. As with the intermediate-length lines, reducing the number of PIPs on a long line reduces both silicon area and capacitance on the long line, thereby reducing RC delay. In some embodiments, special tiles include additional connections between the various interconnect lines to facilitate distribution of high-fanout signals. In some embodiments, global lines having direct access to the logic block inputs are available for global signals such as clocks or other high fanout control signals. In some embodiments, the long lines have connections to each other in the repeatable tile instead of in special tiles.
In some embodiments, the single-length lines are driven by unbuffered PIPs and the intermediate-length and long lines are driven by buffered PIPS. Signals are typically routed on longer buffered interconnect lines first, then fanned out on shorter unbuffered lines. In this manner, large unbuffered RC trees are avoided, making delays on signal paths throughout the FPGA more uniform and improving performance. More uniform delays also make it easier to predict the performance of a circuit earlier in the design cycle.
In accordance with another embodiment of the present invention, the PIPs associated with each tile are programmed in response to configuration data values that are stored in a plurality of configuration memory cells. The configuration memory cells used to configure each tile are arranged in an array having a predetermined number of rows and columns. For example, the configuration memory cell array may include 18 rows and 48 columns of configuration memory cells. The configuration memory cells are preferably laid out adjacent to the elements that they control. For example, configuration memory cells that control the configuration of the logic element are laid out adjacent to the logic element. The configuration memory cells that control the configuration of the interconnect structure are located in rectangular blocks within the array. For example, the configuration memory cells that control the configuration of the interconnect structure may be located in one or more complete rows of the array. This configuration enables the interconnect structure of the tile to be easily modified. For example, to add more interconnect lines to the FPGA, the additional interconnect lines and their associated PIPs are added to the interconnect structure, and the configuration memory cells required to program the new PIPs are added as additional rows in the configuration memory cell array. The pattern of configuration memory cells remains unchanged, except for the added rows of configuration memory cells. The interconnect structure of the tile is therefore easily expandable by adding a rectangular area to the original tile. Moreover, the stream of configuration data values required to program the original FPGA is compatible with the stream of configuration data values required to program the FPGA having the increased interconnect structure.
The compatibility of the configuration bit streams exists because the configuration memory cell array is programmed on a column by column basis. For example, if the original configuration memory cell array has eighteen rows, then eighteen configuration data values are simultaneously loaded into a column of the configuration memory cell array. Similarly, if the expanded configuration memory cell array has twenty rows, then twenty configuration data values are simultaneously loaded into a column of the configuration memory cell array. The streams of configuration data values used to program the eighteen row array and the twenty row array will only differ by the configuration data values associated with the two additional rows in the twenty row array. That is, eighteen configuration data values will match in each of the streams. As a result, the streams of configuration data values of the two tiles are compatible. The stream of configuration data values used to configure the eighteen row array can also be used to configure the twenty row array, as long as xe2x80x9cdon""t programxe2x80x9d values are provided at the two additional row locations.
In another example, interconnect lines are removed from the interconnect structure of the FPGA. To accomplish this, the interconnect lines to be eliminated and their associated PIPs are removed from the interconnect structure. In addition, the configuration memory cells required to program these PIPs are removed, by row, from the first edge of the configuration memory cell array. The pattern of configuration memory cells remains unchanged, except for the removed rows of configuration memory cells. As a result, the tile retains most of its original layout characteristics. Moreover, the stream of configuration data values required to program the FPGA having the reduced interconnect structure is compatible with the stream of configuration data values required to program the original FPGA.
In one embodiment, the interconnect structure is increased or decreased by adding or removing a plurality of intermediate length lines and their associated PIPs. However, in other embodiments, other interconnect resources can be added or removed in accordance with the principles of the present invention.
The present invention will be more fully understood in view of the following description and drawings.